Branch and bound search is used in optimisation situations for tree seadch or {graph search when there is a cost associated with the path taken to reach a solution, and we want to find the solution with the least path cost. The path cost is often additive, for example minimising the number of moves to get to a solution, distances between locations along a geographic route, where each move in a puzzle has a cost. However, branch and bound search does not rely on this, merely that the costs of a path are monotonic, that isnthey increase if the path gets longer. The key insight of branch and bound search is that once we have found best-yet solution, we can prune whole branches for which the path to the branch node exceeds the current best solution. In addition, the path cost to a node can be used as a heuristic to order the open list and choose which nodes to explore first.
Defined on page 69
Used on Chap. 4: pages 69, 70, 74, 80; Chap. 5: page 92; Chap. 11: page 228
Also known as branch and bound
Search tree with path costs